package com.lwx.algorithm.chapter6;

import com.lwx.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Offer94 {
    public static void main(String[] args) {
        TreeNode t = new TreeNode(1, null, null);
        TreeNode t2 = new TreeNode(2, null, null);
        TreeNode root = new TreeNode(3, t, t2);
        Offer94 o = new Offer94();
        List<Integer> ret = o.inorderTraversal(root);
        System.out.println(ret);

    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        Stack<Command> stack = new Stack<>();
        if(root == null){
            return ret;
        }
        stack.push(new Command("go",root));
        while (!stack.isEmpty()) {
            Command current = stack.pop();
            if(current.getS().equals("print")){
                ret.add(current.getNode().getVal());
            }else if(current.getS().equals("go")){
                TreeNode currentNode = current.getNode();
                if(null != currentNode.getRight()){
                    stack.push(new Command("go",currentNode.getRight()));
                }
                stack.push(new Command("print",currentNode));
                if(null != currentNode.getLeft()){
                    stack.push(new Command("go",currentNode.getLeft()));
                }
            }
        }
        return ret;
    }
}
